#include <ctime>
#include "Lista.h"

/* gera inteiro pseudo-aleatorio no intervalo [0,lim]
*  @entradas:
*    lim: limite superior do intervalo
*/
int random_n(int lim){
	return rand() % (lim+1);
}

/* gera vetor de inteiros com valores entre [0,100]
*  @entradas:
*    size: tamanho do vetor
*/
int* radom_array(int size){
	int * ret = new int[size];
	srand(time(NULL));
	for (int i = 0; i < size; i++){
		ret[i] = random_n(100);
	}
	return ret;
}

int max_value(int* my_array, int N){
	int ret = INT_MIN;
	for (int i = 0; i < N; i++){
		if (my_array[i] > ret)
			ret = my_array[i];
	}
	return ret;
}

using namespace std;
/* imprime vetor de inteiros
*  @entradas:
*    my_array: vetor
*	 N: tamanho do vetor
*/
void print_array(int* my_array,int N){
	cout << "[";
	for (int i = 0; i < N; i++){
		cout << my_array[i] << " ";
	}
	cout << "]\n";
}

/* Algoritimo de ordenacao bucketsort
*	ordena vetor de inteiros com valores variando no intervalo [0,k] 
*  @entradas:
*    L: vetor
*	 N: tamanho do vetor
*	 k: maior valor do vetor
*/
void bucket_sort(int* L,int N,int k){
	no** B = new no*[N];
	for (int i = 0; i < N; i++){
		B[i] = NULL;
	}

	for (int i = N-1; i >= 0 ; i--){
		int pos = (L[i] * N) / (k + 1);
		B[pos] = insere(B[pos], L[i]);
	}

	for (int i = 0; i < N; i++){
		print_list(B[i]);
	}

	int j = 0;
	for (int i = 0; i < N; i++){
		B[i] = bubblesort(B[i]);
		
		no* p = B[i];
		while (p != NULL){
			L[j] = p->info;
			j++;
			p = p->proximo;
		}
		free(B[i]);
	}
}

int main(){
	//int* my_array = radom_array(20);
	int my_array[10] = { 44, 21, 49, 2, 14, 4, 36, 64, 57, 13 };
	int K = max_value(my_array, 10);

	cout << "Vetor original:" << endl;
	print_array(my_array, 10);
	
	bucket_sort(my_array, 10, K);

	cout << "Vetor ordenado:" << endl;
	print_array(my_array, 10);
	system("PAUSE");
	return 0;
}